package 背包问题;

public class Solution416 {
    public static void main(String[] args) {
        int[] nums = new int[]{3,3,3,4,5};
        boolean b = canPartition(nums);
        System.out.println(b);

    }

    public static boolean canPartition(int[] nums) {
        int all = 0;
        int maxNum = 0;
        for (int num : nums) {
            all = all + num;
            maxNum = Math.max(maxNum, num);
        }
        if (all % 2 != 0) {
            return false;
        }
        int m = all / 2;
        if (maxNum > m) {
            return false;
        }
        return dp(nums, 0, m) == m;
    }

    //数组，当前位置，目标和
    public static int process(int[] nums, int index, int target) {
        //base case
        if (target < 0) {
            return -1;
        }
        if (index == nums.length) {
            return 0;
        }
        //不拿当前情况
        int p1 = process(nums, index + 1, target);
        //拿当前
        int p2 = 0;
        int next = process(nums, index + 1, target - nums[index]);
        if (next != -1) {
            p2 = nums[index] + next;
        }
        return Math.max(p1, p2);
    }

    //数组，当前位置，目标和
    public static int dp(int[] nums, int index, int target) {
        //base case
        if (nums == null || target == 0) {
            return 0;
        }
        int N = nums.length;
        //index 0~N
        int[][] dp = new int[N + 1][target + 1];

        for (int i = N - 1; i >= 0; i--) {
            for (int rest = 0; rest <= target; rest++) {
                int p1 = dp[i + 1][rest];
                int p2 = 0;
                int next = rest - nums[i] < 0 ? -1 : dp[i + 1][rest - nums[i]];
                if (next != -1) {
                    p2 = next + nums[i];
                }
                int max = Math.max(p1, p2);
                dp[i][rest] = max;
            }
        }
        return dp[0][target];
    }
}
